package LeetcodeTest_forty_one;
//390. 消除游戏
/*
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
* */

import java.util.ArrayList;

public class lastRemaining
{
    public static void main(String[] args)
    {
        System.out.println(solution.lastRemaining(9));
    }
}
class solution
{
    public static int lastRemaining(int n)
    {
        ArrayList<Integer> list=new ArrayList<>();
        int i,j;
        for(i=0;i<n;i++)
            list.add(i+1);
        while (list.size()!=1)
        {
            i=0;
            while (i<list.size())
            {
                list.remove(i);
                i++;
            }
            if(list.size()==1)
                break;
            j=list.size()-1;
            while (j>=0)
            {
                list.remove(j);
                j-=2;
            }
        }
        return list.get(0);
    }
}